# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: radix.py
@time: 2022/7/25 21:32
@author: LDC
"""
'''
5、基数排序（radix sort）
属于“分配式排序”（distribution sort），桶式排序
又称“桶子法”（bucket sort）或bin sort，顾名思义，
它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，
藉以达到排序的作用，基数排序法是属于稳定性的排序，
其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，
在某些时候，基数排序法的效率高于其它的稳定性排序法。
例如：对数组中的元素按照从低位到高位排序，对于[192,221,12,23]
第一轮按照个位数字相同的放在一组，是s[1] =[221],s[2]=[192,12],s[3]=23,
第二轮按照十位数字进行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],
第三轮按照百位数字进行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]
'''
import random
import time


def radixSort(list1, d):
    for i in range(d):  # 多少位数就进行几轮排序
        s = [[] for x in range(10)]  # 因为每一位数字都是0~9，故建立10个桶
        for j in list1:
            s[j // (10 ** i) % 10].append(j)  # 第一次取个位数，第二次取十位数，第三次取百位数
        list1 = [k for t in s for k in t]  # 遍历二维列表s中的元素，赋值给list1
    return list1


if __name__ == '__main__':
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    list2 = radixSort(list1, len(str(max(list1))))
    end1 = time.perf_counter()
    print("基数排序      ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list2 == list4)
